package cn.hutool.core.util;

import cn.hutool.core.bean.BeanUtil;
import cn.hutool.core.collection.CollUtil;

import java.lang.reflect.Field;
import java.security.InvalidParameterException;
import java.util.*;
import java.util.stream.Collectors;

/**
 * <p>集合转树形结构，特点：</p>
 * <ol>
 * 	<li>不需要指定root节点id，自动判断，支持多个root节点</li>
 * 	<li>内置防止循环上下级内存溢出机制，更安全</li>
 * 	<li>支持排序<br>
 * 	<li>不需要创建第三方对象，只要当前集合里的元素存在几个关键字段即可:
 * 	<ol>
 * 		<li>id:唯一标识</li>
 * 		<li>parentId：上级id</li>
 * 		<li>children：存放子节点的集合</li>
 * 	</ol>
 * 	</li>
 * </ol>
 */
public class EasyTreeUtil {

	private EasyTreeUtil() {
	}

	/**
	 * 把列表转换为树结构
	 *
	 * @param originalList      原始list数据
	 * @param keyName           作为唯一标示的字段名称
	 * @param parentFieldName   父节点字段名称
	 * @param childrenFieldName 子节点字段名称
	 * @param sortFieldName     排序字段名
	 * @param ascending         true-升序；false-降序
	 * @return 组装后的集合
	 */
	public static <T> List<T> buildTree(List<T> originalList, String keyName, String parentFieldName, String childrenFieldName, String sortFieldName, boolean ascending) {
		if (CollUtil.isEmpty(originalList)) {
			return originalList;
		}
		//入参校验
		validateFieldExistence(originalList.get(0), keyName, parentFieldName, childrenFieldName, sortFieldName);

		// 查找出根节点列表
		Set<T> rootSet = findRootNodes(originalList, keyName, parentFieldName);

		List<T> rootList = new ArrayList<>(rootSet);
		if (CollUtil.isEmpty(rootList)) {
			return rootList;
		}
		//对root节点排序
		sortByField(rootList, sortFieldName, ascending);

		//移除根节点，减少循环次数
		originalList.removeAll(rootSet);

		// 递归封装树
		fillTree(rootList, originalList, keyName, parentFieldName, childrenFieldName, sortFieldName, ascending);

		return rootList;
	}

	/**
	 * 查询所有根节点
	 *
	 * @param originalList    原始list数据
	 * @param keyName         作为唯一标示的字段名称
	 * @param parentFieldName 父节点字段名称
	 * @return Set 所有根节点
	 */
	private static <T> Set<T> findRootNodes(List<T> originalList, String keyName, String parentFieldName) {
		Set<T> rootSet = new HashSet<>();
		Map<Object, T> objMap = originalList.stream().collect(Collectors.toMap(item -> BeanUtil.getProperty(item, keyName), s -> s, (s1, s2) -> s1));
		//存储访问过的对象，防止循环上下级递归导致内存溢出
		List<Object> visitedList = new ArrayList<>();
		for (T t : originalList) {
			T top = findRootNode(objMap, t, parentFieldName, visitedList);
			if (top == null) {
				continue;
			}
			rootSet.add(top);
		}
		return rootSet;
	}


	/**
	 * 递归获取root节点
	 * 成为root节点的条件：parentField的值为空|在objMap集合里不存在|为0|为空字符串
	 *
	 * @param objMap          原始集合
	 * @param obj             当前obj
	 * @param parentFieldName 父节点字段名称
	 * @param visitedList     存储已访问过的节点，用于防止循环上下级导致内存溢出
	 * @return root节点
	 */
	private static <T> T findRootNode(Map<Object, T> objMap, T obj, String parentFieldName, List<Object> visitedList) {
		Object parentFieldVal = BeanUtil.getProperty(obj, parentFieldName);
		if (parentFieldVal == null) {
			return obj;
		}
		if (StrUtil.isBlankIfStr(parentFieldVal)) {
			return obj;
		}
		//判断判断是否为0
		if (isParentFieldZero(parentFieldVal)) {
			return obj;
		}

		T t = objMap.get(parentFieldVal);
		if (t == null) {
			return obj;
		}
		if (visitedList.contains(parentFieldVal)) {
			return null;
		}
		visitedList.add(parentFieldVal);
		return findRootNode(objMap, t, parentFieldName, visitedList);
	}


	/**
	 * 封装树
	 *
	 * @param parentList        要封装为树的父对象集合
	 * @param originalList      原始list数据
	 * @param keyName           作为唯一标示的字段名称
	 * @param parentFieldName   模型中作为parent字段名称
	 * @param childrenFieldName 模型中作为children的字段名称
	 */
	private static <T> void fillTree(List<T> parentList, List<T> originalList, String keyName, String parentFieldName, String childrenFieldName, String sortFieldName, boolean ascending) {
		for (T t : parentList) {
			List<T> children = fillChildren(t, originalList, keyName, parentFieldName, childrenFieldName, sortFieldName, ascending);
			if (children.isEmpty()) {
				continue;
			}
			originalList.removeAll(children);
			fillTree(children, originalList, keyName, parentFieldName, childrenFieldName, sortFieldName, ascending);
		}
	}

	/**
	 * 封装子对象
	 *
	 * @param parent            父对象
	 * @param originalList      待处理对象集合
	 * @param keyName           作为唯一标示的字段名称
	 * @param parentFieldName   模型中作为parent字段名称
	 * @param childrenFieldName 模型中作为children的字段名称
	 * @return 父对象的子节点集合
	 */
	private static <T> List<T> fillChildren(T parent, List<T> originalList, String keyName, String parentFieldName, String childrenFieldName, String sortFieldName, boolean ascending) {
		List<T> childList = new ArrayList<>();
		Object val = BeanUtil.getProperty(parent, keyName);
		for (T t : originalList) {
			Object childParentVal = BeanUtil.getProperty(t, parentFieldName);
			if (val.equals(childParentVal)) {
				childList.add(t);
			}
		}
		if (!childList.isEmpty()) {
			//排序
			sortByField(childList, sortFieldName, ascending);
			//赋值
			ReflectUtil.setFieldValue(parent, childrenFieldName, childList);
		}
		return childList;
	}


	/**
	 * 判断parentField的值是否为0
	 *
	 * @param parentFieldValue parent值
	 * @return 如果为Number是否为0
	 */
	private static boolean isParentFieldZero(Object parentFieldValue) {
		if (parentFieldValue instanceof String) {
			if (NumberUtil.isNumber((String) parentFieldValue)) {
				Number parentFieldNumberVal = NumberUtil.parseNumber((String) parentFieldValue);
				return parentFieldNumberVal.doubleValue() == 0;
			}
		}
		if (parentFieldValue instanceof Number) {
			return ((Number) parentFieldValue).doubleValue() == 0;
		}
		return false;
	}

	/**
	 * 排序
	 *
	 * @param list      需要排序的集合
	 * @param fieldName 排序指定的字段
	 * @param ascending 是否升序
	 */
	private static void sortByField(List<?> list, String fieldName, boolean ascending) {
		if (CollUtil.isEmpty(list)) {
			return;
		}
		if (StrUtil.isBlank(fieldName)) {
			return;
		}
		//使用反射获取指定字段
		try {
			Field field = list.get(0).getClass().getDeclaredField(fieldName);
			field.setAccessible(true);
			// 使用匿名Comparator类根据指定字段进行排序
			Collections.sort(list, (Comparator<Object>) (o1, o2) -> {
				try {
					Comparable fieldValue1 = (Comparable) field.get(o1);
					Comparable fieldValue2 = (Comparable) field.get(o2);
					//排序字段为空，默认放最后面
					if (fieldValue1 == null) {
						return 1;
					}
					int result = fieldValue1.compareTo(fieldValue2);
					//根据排序方式返回结果
					return ascending ? result : -result;
				} catch (IllegalAccessException e) {
					throw new RuntimeException(e);
				}
			});

		} catch (NoSuchFieldException e) {
			throw new IllegalArgumentException("指定的排序字段不存在：" + fieldName, e);
		}
	}


	/**
	 * @param obj               要检查的对象
	 * @param keyName           作为唯一标示的字段名称
	 * @param parentFieldName   父节点字段名称
	 * @param childrenFieldName 子节点字段名称
	 * @param sortFieldName     排序字段名
	 * @param childrenFieldName 子节点字段名称
	 * @param <T>
	 */
	private static <T> void validateFieldExistence(T obj, String keyName, String parentFieldName, String childrenFieldName, String sortFieldName) {
		if (!validateFieldExistence(obj, keyName)) {
			throw new InvalidParameterException("keyName参数无效");
		}
		if (!validateFieldExistence(obj, parentFieldName)) {
			throw new InvalidParameterException("parentFieldName参数无效");
		}
		if (!validateFieldExistence(obj, childrenFieldName)) {
			throw new InvalidParameterException("childrenFieldName参数无效");
		}
		if (StrUtil.isNotBlank(sortFieldName) && !validateFieldExistence(obj, sortFieldName)) {
			throw new InvalidParameterException("sortFieldName参数无效");
		}
	}

	/**
	 * 校验字段是否存在
	 *
	 * @param obj       对象
	 * @param fieldName 要检查的字段名
	 * @param <T>
	 * @return 字段名在对象里是否存在
	 */
	private static <T> boolean validateFieldExistence(T obj, String fieldName) {
		if (StrUtil.isBlank(fieldName)) {
			return false;
		}
		try {
			Class<?> clazz = obj.getClass();
			clazz.getDeclaredField(fieldName);
			return true;
		} catch (NoSuchFieldException e) {

		}
		return false;
	}

}
